#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 从小到大排序
// https://blog.csdn.net/justidle/article/details/104203963
void qsort(vector<int> &nums, int left, int right) {
    if (left >= right) return;
    int l = left, r = right, base = nums[left];
    while (l < r) {
        while (nums[r] >= base && l < r) r--;
        while (nums[l] <= base && l < r) l++;
        if (l < r) swap(nums[l], nums[r]);
    }
    swap(nums[l], nums[left]);
    qsort(nums, left, l - 1);
    qsort(nums, l + 1, right);
}

// 从大到小排序
void qsort1(vector<int> &nums, int left, int right) {
    if (left >= right) return;
    int l = left, r = right, base = nums[left];
    while (l < r) {
        while (nums[r] <= base) r--;
        while (nums[l] > base) l++;
        if (l < r) swap(nums[r--], nums[l++]);
    }
    nums[l] = base;
    qsort1(nums, left, l - 1);
    qsort1(nums, l + 1, right);
}


int main() {
    vector<int> nums = {187, 8559, 3718, 3741, 99, -1, 286, 1, 3, 1217, 1531, 8056, 6, 8649, 9746};
    for (auto i : nums) {
        cout << i << ",";
    }
    cout << endl;
    qsort(nums, 0, nums.size() - 1);
    cout << "sorted:" << endl;
    for (auto i : nums) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}